package com.fr.lintcode;

import org.junit.Test;

public class Q614 {

    /**
     * @param root: the root of binary tree
     * @return: the length of the longest consecutive sequence path
     */
    public int longestConsecutive2(TreeNode root) {
        // write your code here
    	int max = 0;
    	if(root == null) {
    		return 0;
    	}
    	if(root.left == null && root.right == null) {
    		return 1;
    	}
    	if (root.left == null || root.right == null) {
    		max = Math.max(longestConsecutive2(root.left), longestConsecutive2(root.right));
    		return max;
    	}
    	int left = longestConsecutive2(root.left);
    	int right = longestConsecutive2(root.right);
    	if(root.left.val != root.right.val) {
    		max = left + right;
    	}else {
    		max = Math.max(left, right);
    	}
    	return max;
    }
    
    @Test
    public void tesA() {
    	TreeNode n1 = new TreeNode(1);
    	TreeNode n2 = new TreeNode(2);
    	TreeNode n3 = new TreeNode(3);
    	TreeNode n4 = new TreeNode(4);
    	TreeNode n5 = new TreeNode(5);
    	n1.left = n2;
    	n2.right = n3;
    	n1.right = n5;
    	n2.left = n4;
    	System.out.println(longestConsecutive2(n1));
    }

}
